package 题目集.滑动窗口.ch02_不定长窗口;

import org.junit.Test;

/**
 * 思维题：
 * 给你一个正整数数组 arr，和一个整数k
 * 问arr中，有多少个区间，其区间内数字的种类为K种。
 * https://leetcode.cn/problems/subarrays-with-k-different-integers/description/
 */
public class ch06_K个不同整数的子数组 {
    /**
     * 暴力思路：
     *      1.枚举每一个起点对应的每一个区间。查看区间内的数字种类是否为K种。
     *      时间复杂度：枚举行为O(n^2)，查看区间内的数字种类为O(n)，查看种类可以优化为O(1)，所以总的时间复杂度为O(n^2)
     * 滑动窗口思路：
     *      如果求区间内数字种类严格=k的区间数量，滑动窗口并不好求，但是求区间内数字种类<=k的区间数量是好求的。
     *      我们可以求区间内数字种类<=k的区间数量，然后减去区间内数字种类<=k-1的区间数量。得到的结果就是区间内数字种类=k的区间数量。
     *      所以问题转化为：求区间内数字种类<=k的区间数量。
     *          如果找到一个数字种类为k的区间[l,r)。
     *          那么以l为起点的，符合条件的区间数量为r-l,
     *          所以找所有区间内数字种类<=k的区间数量，就是 “找到所有数字种类=k的最长区间”。
     */

    public int subarraysWithKDistinct(int[] nums, int k) {
        return nums(nums, k) - nums(nums, k - 1);
    }

    static int[] count = new int[2 * 10000 + 1];  //记录每个数字在窗口中出现的次数
    /**
     * 求区间内数字种类<=k的区间数量。
     * 即找到所有数字种类=k的最长区间。
     */
    public int nums(int[] nums, int k) {
        int res = 0;
        int i = 0, j = 0;
        int cnt = 0;  //记录区间内数字种类
        for (; j < nums.length; j++) {
            if (count[nums[j]]++ == 0) {    //新加入的种类
                cnt++;
            }
            while (cnt > k) {   //移除到下一个数字种类<=k的窗口
                res += j - i;   //不包括r所以不用额外加1
                if (count[nums[i]] == 1) {  //被移除的数只在窗口中出现过一次
                    cnt--;
                }
                count[nums[i++]]--;
            }
        }
        //将最后一个区间内的所有子区间数量加上
        while (i<j){
            res+=j-i;
            count[nums[i++]]--;
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = {1, 2, 1, 2, 3};
        int k = 2;
        System.out.println(subarraysWithKDistinct(nums, k));
    }
}
